COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	 balance.2[f81,jmc]	Functions for balancing S-expressions
C00005 ENDMK
C⊗;
;;; balance.2[f81,jmc]	Functions for balancing S-expressions
;;; The value of  b x  is the the result of balancing  x  paired with
;;; the depth of this result.  Here it is in external form using
;;; multiple output functions.

;;; b x ← if at x then x,0
;;;	else {b a x, b d x}[λy m z n.if |m-n|≤1 then y.z,max(m,n)+1
;;;				else if m<n then{b[y . a z]}[λ w p. w . d z,
;;; max(p+1,n)
;;;				else {b[d y . z]}[λw p. a y . w, max(m,p+1)

;;; The internal version has to simulate the multiple outputs by pairing.

;;; These two should be in elisp.ini, but ...
(defun if macro (l)(cons 'cond (ifxxx1 (cdr l))))

(defun ifxxx1 (u) (cond ((null u) nil) ((null (cdr u)) (list (list t (car u))))
(t (cons (list (car u) (cadr u)) (ifxxx1 (cddr u))))))

(defun b (x)
       (if (atom x) (cons x 0)
	   ((lambda (y z)
		    (if (lessp (abs (difference (cdr y) (cdr z))) 2)
			(cons (cons (car y) (car z))
			      (add1 (max (cdr y) (cdr z))))
			(lessp (cdr y) (cdr z))
			((lambda (w)
				 (cons (cons (car w) (cdar z))
				       (max (add1 (cdr w)) (cdr z))))
			 (b (cons (car y) (caar z))))
			((lambda (w)
				 (cons (cons (caar y) (car w))
				       (max (cdr y) (add1 (cdr w)))))
			 (b (cons (cdar y) (car z))))))
	    (b (car x)) (b (cdr x)))))

(b 'a)
B 
B 
(A . 0.) 
(b '(a.b))
((A . B) . 1.) 
(b '(a.(b.c)))
((A B . C) . 2.) 
(b '(a.(b.(c.d))))
(((A . B) C . D) . 2.)